package com.algorithm.cjm.jiaocai.ch5;

/**
 * Created by jieming.chen on 2020/2/6
 */
public class Example27 {

    public static void main(String[] args) {
        Example27 example27 = new Example27();

        String a = "ABCBDAB";
        String b = "BCDB";
        String s = example27.build_lcs(a, b);
        System.out.println(s);

        String a1 = "BDCABA";
        String b1 = "ABCBDAB";
        String s1 = example27.build_lcs(a1, b1);
        System.out.println(s1);
    }

    String build_lcs(String a, String b) {
        int[][] c = lcs_len(a, b);
        int i = a.length(), j = b.length();
        int k = c[i][j];
        char[] str = new char[k];
        while (k > 0) {
            if (c[i][j] == c[i-1][j]) {
                i = i - 1;
            } else if (c[i][j] == c[i][j -1]) {
                j = j - 1;
            } else {
                k--;
                str[k] = a.charAt(i -1);
                i = i - 1;
            }
        }
        return String.valueOf(str);
    }

    int[][] lcs_len(String a, String b) {
        int m = a.length(), n = b.length();
        int[][] c = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            c[i][0] = 0;
        }
        for (int i = 0; i <=n; i++) {
            c[0][i] = 0;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (a.charAt(i - 1) == b.charAt(j-1)) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                } else {
                    c[i][j] = Math.max(c[i-1][j], c[i][j -1]);
                }
            }
        }
        return c;
    }

}
